package ch5.part2;

import java.util.HashSet;

/**
 * 排查单链表中是否存在循环死结
 * isCycleWithPointer: 快慢针法
 * isCycleWithHashSet: Set法
 *
 * @author liuwanxiang
 * @version 2019/06/17
 */
public class CycleLinkedList {

    /**
     * 快慢针排查法：存在死结循环，则为追击问题，必然会存在某一时刻相遇
     * 时间复杂度：O(n) = n
     * 空间复杂度：O(n) = 1
     *
     * @param head 头结点
     * @return 是否存在循环死结
     */
    private static boolean isCycleWithPointer(Node head) {
        Node p1 = head, p2 = head;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            if (p1 == p2) {
                return true;
            }
        }
        return false;
    }

    /**
     * 通过HashSet来存储已访问过的节点，用以判重
     * 时间复杂度：O(n) = n
     * 空间复杂度：O(n) = n
     *
     * @param head 头结点
     * @return 是否存在循环死结
     */
    private static boolean isCycleWithHashSet(Node head) {
        HashSet<Node> visitedNodes = new HashSet<>();
        for (Node pointer = head; pointer.next != null; pointer = pointer.next) {
            if (!visitedNodes.add(pointer)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 通过追击问题计算环的长度
     *
     * @param head 头结点
     * @return 环长度，无环时，长度为0
     */
    private static int calcCycleLength(Node head) {
        Node p1 = head, p2 = head;
        int firstMeet = 0, secondMeet = 0;
        int i = 0;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;

            i++;
            if (p1 == p2 && firstMeet == 0) {
                firstMeet = i;
                continue;
            }
            if (p1 == p2) {
                secondMeet = i;
                break;
            }
        }
        return secondMeet - firstMeet;
    }

    /**
     * 利用快慢指针，找环节点的起始Index
     * 设：a为head到入环点的距离，b为入环点到初次相遇点的距离
     * c为初次相遇点到入环点的距离
     * <p>
     * 根据calcCycleLength此方法，可得 2(a+b) = a+b+c+b
     * 整理算式可得，a=c
     * <p>
     * 故当p1从head节点开始遍历，p2从首次相遇点开始遍历
     * 步长均为1，则p1、p2势必会在入环点相遇
     * 且此时p1、p2走过的长度，即为入环点的Index
     *
     * @param head 链表头结点
     * @return 环节点的起始Index
     */
    private static int calcCycleStart(Node head) {
        Node p1 = head, p2 = head;
        boolean isCycle = false;

        // 利用快慢指针，将p2指针指向相遇点
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            if (p1 == p2) {
                isCycle = true;
                break;
            }
        }

        // 如果链表无环，返回-1
        if (!isCycle) {
            return -1;
        }

        // p1指针拨回到头结点，p1,p2重新以相同步长进行遍历
        // p1、p2重新相遇时，该节点即为链表环起始节点
        // 走过的长度，即为该节点的Index
        p1 = head;
        int location = 0;
        while (p1 != p2 && p2 != null) {
            p1 = p1.next;
            p2 = p2.next;
            location++;
        }
        return location;
    }

    private static class Node {
        private int data;
        private Node next;

        Node(int data) {
            this.data = data;
        }

        @Override
        public int hashCode() {
            return super.hashCode();
        }

        @Override
        public boolean equals(Object obj) {
            return super.equals(obj);
        }
    }

    public static void main(String[] args) {
        Node n1 = new Node(5), n2 = new Node(3), n3 = new Node(7),
                n4 = new Node(2), n5 = new Node(6),
                n6 = new Node(8), n7 = new Node(1);

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n7;
        n7.next = n4;

        System.out.println(isCycleWithPointer(n1));
        System.out.println(isCycleWithHashSet(n1));

        System.out.println(calcCycleLength(n1));
        System.out.println(calcCycleStart(n1));
    }


}
